package com.suanfa.search;

/**
 * Created by buguniao on 16/2/28.
 */
public class RedBlackBST {
    public int RED=0;
    public int BLACK=1;

    private class Node{
        private String key;
        private int value;
        private int N;
        private Node left;
        private Node right;
        private int color;

        public Node(String key,int value,int N){
            this.key=key;
            this.value=value;
            this.N=N;
            this.color=RED;
        }
    }
    private Node root;

    public int get(String key){
        return get(root,key);
    }
    private int get(Node h,String key){
        if(h==null){
            return -1;
        }
        int comp = key.compareTo(h.key);
        if(comp<0){
            return get(h.left,key);
        }else if(comp>0){
           return get(h.right,key);
        }else{
            return h.value;
        }
    }
    public void put(String key,int value){
        root = put(root,key,value);
        root.color=BLACK;
    }
    private Node put(Node h,String key,int value){
        if(h==null){
            return new Node(key,value,1);
        }
        int comp = key.compareTo(h.key);
        if(comp<0){
            h.left = put(h.left,key,value);
        }else if(comp >0){
            h.right = put(h.right,key,value);
        }else{
            h.value=value;
        }
        if(isRed(h.right) && !isRed(h.left)){
           h= rotateLeft(h);
        }
        if(isRed(h.left) && isRed(h.left.left)){
           h= rotateRight(h);
        }
        if(isRed(h.left) && isRed(h.right)){
            flipColor(h);
        }

        h.N=size(h);
        return h;
    }
    public boolean isRed(Node h){
        if(h==null){
            return false;
        }
        return h.color==RED;
    }
    public int size(Node h){
        if(h==null){
            return 0;
        }
        return size(h.left)+size(h.right)+1;
    }
    public Node rotateLeft(Node h){
        Node x= h.right;
        h.right=x.left;
        x.left=h;
        x.color=h.color;
        h.color=RED;
        x.N=h.N;
        h.N=size(h);
        return x;

    }
    public Node rotateRight(Node h){
        Node x = h.left;
        h.left=x.right;
        x.right=h;
        x.color=h.color;
        h.color=RED;
        x.N=h.N;
        h.N=size(h);
        return x;
    }
    public void flipColor(Node h){
        if(h==null){
            return;
        }
        if(h.left!=null){
            h.left.color=BLACK;
        }
        if(h.right!=null){
            h.right.color=BLACK;
        }
        h.color=RED;
    }

    public static void main(String[] args){
        RedBlackBST bst = new RedBlackBST();
        bst.put("e",10);
        bst.put("a",20);
        bst.put("c",30);
        bst.put("r",40);
        bst.put("s",50);
        bst.put("h",60);

        System.out.println(bst.get("d"));
    }
}
